package fun.ticsmyc.question.dp;

import java.util.HashMap;
import java.util.Map;

/**
 * 887. 鸡蛋掉落
 * @author Ticsmyc
 * @package fun.ticsmyc.question.dp
 * @date 2021-02-06 12:23
 */
public class 扔鸡蛋 {

    /**
     * 超时的递归+备忘录
     * O( K * N^2 )
     */
    Map<String,Integer> book = new HashMap<>();
    public int superEggDrop(int K, int N) {
        if(N==0) return 0;
        if(K==1) return N;
        if(book.containsKey(K+"#"+N)){
            return book.get(K+"#"+N);
        }
        int r=Integer.MAX_VALUE;
        for(int i=1;i<=N;++i){
            r= Math.min(r ,Math.max( superEggDrop(K,N-i) , superEggDrop(K-1,i-1))+1);
        }
        book.put(K+"#"+N,r);
        return r;
    }

    //TODO : dp待填坑
}
